package leetcode.code;

import java.util.Arrays;

/**
 * 给出一个二维整数网格 grid，网格中的每个值表示该位置处的网格块的颜色。
 *
 * 只有当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。
 *
 * 连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻（四个方向上）的所有正方形，或者在网格的边界上（第一行/列或最后一行/列）的所有正方形。
 *
 * 给出位于 (r0, c0) 的网格块和颜色 color，使用指定颜色 color 为所给网格块的连通分量的边界进行着色，并返回最终的网格 grid 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
 * 输出：[[3, 3], [3, 2]]
 * 示例 2：
 *
 * 输入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
 * 输出：[[1, 3, 3], [2, 3, 3]]
 * 示例 3：
 *
 * 输入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
 * 输出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]
 *  
 *
 * 提示：
 *
 * 1 <= grid.length <= 50
 * 1 <= grid[0].length <= 50
 * 1 <= grid[i][j] <= 1000
 * 0 <= r0 < grid.length
 * 0 <= c0 < grid[0].length
 * 1 <= color <= 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coloring-a-border
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class medium_边框着色 {

    static class Solution {
        public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
            boolean[][] flags = new boolean[grid.length][grid[0].length];
            int len = grid[0].length;
            dfs(grid, r0, c0, grid[r0][c0], flags);
            for (int r = 0; r < grid.length; r++){
                for (int c = 0; c < len; c++){
                    if (flags[r][c] &&
                            !(r-1>=0 && r+1<grid.length && c-1>=0 && c+1<len
                                    && flags[r-1][c] && flags[r+1][c] && flags[r][c-1] &&flags[r][c+1]))
                        grid[r][c] = color;
                }
            }
            return grid;
        }

        private void dfs(int[][] grid, int r, int c, int origin, boolean[][] flags){
            flags[r][c] = true;
            if(c-1>=0 && grid[r][c-1]==origin && !flags[r][c-1]){
                dfs(grid, r, c-1, origin, flags);
            }
            if(c+1<grid[0].length && grid[r][c+1]==origin && !flags[r][c+1]){
                dfs(grid, r, c+1, origin, flags);
            }
            if(r-1>=0 && grid[r-1][c]==origin && !flags[r-1][c]){
                dfs(grid, r-1, c, origin, flags);
            }
            if(r+1<grid.length && grid[r+1][c]==origin && !flags[r+1][c]){
                dfs(grid, r+1, c, origin, flags);
            }
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.colorBorder(new int[][]{{1,1,1},{1,1,1},{1,1,1}}, 1, 1,  2)[1]));
    }
}
